package com.nine.algorithm.recursion.binarysearch;

/**
 * @author nine
 * @version 1.0
 * @description 递归实现二分查找
 * @date 24/4/30 22:36
 */
public class BinarySearch {

	public static int search(int[] a, int target) {
		return f(a, target, 0, a.length - 1);
	}

	/**
	 * 递归（子问题）函数
	 *
	 * @param a      数组
	 * @param target 目标值
	 * @param i      起始索引（包含）
	 * @param j      结束索引（包含）
	 * @return 返回索引，找不到返回-1
	 */
	private static int f(int[] a, int target, int i, int j) {
		// 递归先找出口
		if (i > j) {
			return -1;
		}

		// 中间数
		int m = (i + j) >>> 1;
		if (target < a[m]) {
			return f(a, target, i, m - 1);
		}
		else if (a[m] < target) {
			return f(a, target, m + 1, j);
		}
		else {
			return m;
		}
	}

}
